The invention relates to automated paragraph layout.
Paragraph layout in a document production application involves selection and placement of line breaks to produce a visually pleasing appearance within a paragraph cell that defines the space allotted for the paragraph. Changes in the style of the text, e.g., fonts, formats, line heights, and point size, can complicate the task, particularly when layout is performed within arbitrary shapes. In particular, paragraph cells with arbitrary shapes can produce baselines that vary in width. Text style changes and shape complexity can significantly increase computational overhead and processing time.
A number of techniques exist for automated paragraph layout. Many involve the formulation of a search tree structure representing all possible line combinations for a given paragraph. This type of technique assigns a penalty value to each possible line, and picks a path through the tree with the lowest accrued penalty. Although this technique is generally effective, it is very time- and memory-intensive. Extensive use of system resources and protracted processing time is generally undesirable in document production, especially in light of the increasing complexities of document content.
Other techniques make use of dynamic programming and failure functions to create algorithms that run in linear time. Dynamic programming techniques generally are less memory-intensive and very quick. Complex shapes can undermine the effectiveness of such techniques, however, limiting their general application to paragraph layout. In particular, some dynamic programming techniques are inapplicable for shapes that deviate from a constant baseline width.